home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / LIBIP / XYTOLINE.C < prev    next >
C/C++ Source or Header  |  1999-09-11  |  6KB  |  180 lines
  1. /* 
  2.  * xytoline.c
  3.  * 
  4.  * Practical Algorithms for Image Analysis
  5.  * 
  6.  * Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
  7.  */
  8.  
  9. /* XYTOLINE:    function takes input stream of (x,y) coordinates in chains
  10.  *            that may be broken by break features, and orders them through
  11.  *              the breaks.
  12.  *                      usage: xytoline (data, &nData, &nSegments, &nStructs)
  13.  */
  14.  
  15. #include <stdio.h>
  16. #include <stdlib.h>
  17. #include <images.h>
  18. #include "pcc2.h"               /* header file for PCC programs */
  19.  
  20. long
  21. xytoline (data, nData, nSegments, nStructs)
  22.      struct point *data;        /* data curve */
  23.      long *nData;               /* no. coords in data curve */
  24.      long *nSegments;           /* no. of segments found */
  25.      long *nStructs;            /* no. of structures found */
  26. {
  27.   struct point *data2;          /* second data curve */
  28.   long nData2;                  /* no. of data coordinates after reorg. */
  29.   long feature;                 /* value of PCC feature */
  30.   long strtBr, endBr;           /* data indices to start, end of line break */
  31.   long endStruct;               /* end index of current structure */
  32.   long iStrt;                   /* starting index into data vector */
  33.   long length, maxLength;       /* maximum length segment completes break */
  34.   long endStrt;                 /* flag = 1 if end joined to start;
  35.                                  * * = 2 if start joined to start; 0 unjoined */
  36.   long iStrtMax, iEndMax;       /* start and end of break completion */
  37.   long endStrtMax;              /* end-to-start joint type of max segment */
  38.   long i, j;
  39.  
  40. /* initialize second data vector */
  41.   if ((data2 = (struct point *)
  42.        calloc (*nData, sizeof (struct point))) == NULL) {
  43.     printf ("XYTOLINE: not enough memory -- sorry");
  44.     return (-1);
  45.   }
  46.   for (i = 0; i < *nData; i++) {
  47.     data2[i].x = data[i].x;
  48.     data2[i].y = data[i].y;
  49.   }
  50.   nData2 = 0;
  51.   *nSegments = 0;
  52.   *nStructs = 0;
  53.  
  54. /* extract line segments from data stream */
  55. /* the only complication is that the two segments comprising a LINEBREAK */
  56. /* must be joined up */
  57.  
  58.   for (i = 0; i < *nData; i++) {
  59.  
  60.     feature = data2[i].x;       /* first in each segment must be feature */
  61.     if (feature > 0);           /*printf ("ERROR -- expecting feature = %d", feature); */
  62.  
  63.     else if (feature == -STOPCODE)
  64.       break;
  65.  
  66.     else if (feature != -LINEBRCODE) {  /* not LINEBRCODE: just copy segment */
  67.       if (feature <= -STARTCODE)
  68.         (*nStructs)++;
  69.       if (data2[i + 1].x >= 0) {  /* non-zero segment length */
  70.         data[nData2++].x = -1;
  71.         (*nSegments)++;
  72.         i++;
  73.         while (data2[i].x >= 0) {
  74.           data[nData2].x = data2[i].x;
  75.           data[nData2++].y = data2[i++].y;
  76.         }
  77.         --i;
  78.       }
  79.     }
  80.  
  81.     /* LINEBREAK segment -- store start and end, then find second half. */
  82.     /* Second half segment of linebreak is chosen as the segment before */
  83.     /* the start of the next structure, which is the longest segment that */
  84.     /* starts or ends at the starting location of the break. (got that?) */
  85.  
  86.     else if (feature == -LINEBRCODE) {
  87.       (*nStructs)++;
  88.  
  89.       /* determine first LINEBR segment */
  90.       endStrt = endStrtMax = 0;
  91.       strtBr = i + 1;
  92.       for (j = strtBr; j < *nData; j++)
  93.         if (data2[j].x < 0)
  94.           break;
  95.       endBr = j - 1;
  96.  
  97.       /* determine end of structure */
  98.       for (; j < *nData; j++)
  99.         if (data2[j].x <= -STARTCODE)
  100.           break;
  101.       endStruct = j - 1;
  102.       i = endStruct;
  103.  
  104.       /* find longest segment adjoining LINEBREAK segment */
  105.       length = maxLength = 0;
  106.       iStrt = endBr + 2;
  107.       endStrt = endStrtMax = 0;
  108.       for (j = iStrt; j <= endStruct; j++) {
  109.         if (data2[j].x > 0)
  110.           length++;
  111.         else {
  112.           if (length > 0) {
  113.             if ((ABS (data2[j - 1].x - data2[strtBr].x) <= 1)
  114.                 && (ABS (data2[j - 1].y - data2[strtBr].y) <= 1))
  115.               endStrt = 1;
  116.             else if ((ABS (data2[iStrt].x - data2[strtBr].x) <= 1)
  117.                      && (ABS (data2[iStrt].y - data2[strtBr].y) <= 1))
  118.               endStrt = 2;
  119.             if (endStrt != 0) {
  120.               if (length > maxLength) {  /* choose longest break end */
  121.                 maxLength = length;
  122.                 iStrtMax = iStrt;
  123.                 iEndMax = j - 1;
  124.                 endStrtMax = endStrt;
  125.               }
  126.             }
  127.           }
  128.           iStrt = j + 1;
  129.           length = 0;
  130.         }
  131.       }
  132.  
  133.       /* copy adjoining segment, either backwards or forwards, then line break */
  134.       data[nData2++].x = -1;
  135.       if (endStrtMax == 1) {
  136.         for (j = iStrtMax; j <= iEndMax; j++) {
  137.           data[nData2].x = data2[j].x;
  138.           data[nData2++].y = data2[j].y;
  139.         }
  140.       }
  141.       else if (endStrtMax == 2) {
  142.         for (j = iEndMax; j >= iStrtMax; --j) {
  143.           data[nData2].x = data2[j].x;
  144.           data[nData2++].y = data2[j].y;
  145.         }
  146.       }
  147.       for (j = strtBr; j <= endBr; j++) {
  148.         data[nData2].x = data2[j].x;
  149.         data[nData2++].y = data2[j].y;
  150.       }
  151.       (*nSegments)++;
  152.  
  153.       /* copy other segments */
  154.       for (j = endBr + 1; j < endStruct; j++) {
  155.         if (data2[j].x < 0) {
  156.           if (j == (iStrtMax - 1))
  157.             j = iEndMax;
  158.           else {
  159.             data[nData2++].x = -1;
  160.             (*nSegments)++;
  161.             j++;
  162.             while (data2[j].x >= 0) {
  163.               data[nData2].x = data2[j].x;
  164.               data[nData2++].y = data2[j++].y;
  165.             }
  166.             --j;
  167.           }
  168.         }
  169.       }
  170.  
  171.     }
  172.   }
  173.  
  174.   if (data[nData2 - 1].x >= 0)
  175.     data[nData2++].x = -1;
  176.   *nData = nData2;
  177.  
  178.   return (0);
  179. }
  180.